`
https://leetcode.cn/problems/russian-doll-envelopes/
`

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
var maxEnvelopes = function (envelopes) {
  // 先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序
  // 之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案
  // 相当于先保证 w 是能够嵌套的，然后只需要专注高度 h 这个维度能够互相嵌套即可
  // 相同的 w 要让 h 倒序是因为：两个 w 相同的信封不能相互包含
  const n = envelopes.length
  envelopes.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : a[0] - b[0])

  // 高度单独提出来
  const heights = Array.from({ length: n }, (_, i) => envelopes[i][1])

  return lengthOfLIS(heights)
};

function lengthOfLIS(nums) {
  const top = new Array(nums.length);
  let piles = 0
  for (let i = 0; i < nums.length; i++) {
    const poker = nums[i]
    let left = 0, right = piles
    while (left < right) {
      const mid = Math.floor((left + right) / 2)
      if (top[mid] < poker) {
        left = mid + 1
      } else {
        right = mid
      }
    }
    if (left == piles) piles++
    top[left] = poker
  }
  return piles
};